package lib.random;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Set;
import lib.datatypes.TwoDimensionalLongPoint;

/**
 * Generates random points on a grid
 * @author dolphinigle
 */
public class RandomPoints {

  /**
   * Random provider
   */

  private ExtendedRandom random_;

  /**
   * Generates points related random stuffs
   * @param random random provider
   */
  public RandomPoints(ExtendedRandom random) {
    random_ = random;
  }

  /**
   * Generates some points on 2D plane that are distinct
   * @param n number of points
   * @param lower_bound minimum value of x and y coordinates
   * @param upper_bound maximum value of x and y coordinates
   * @return
   */
  public TwoDimensionalLongPoint[] 
          GenerateDistinctTwoDimensionalLongPoints(
          int n, long lower_bound, long upper_bound) {
    TwoDimensionalLongPoint[] ret = new TwoDimensionalLongPoint[n];
    
    // determine which algorithm to use
    if (upper_bound - lower_bound + 1 > 2 * n ||
            (upper_bound - lower_bound + 1) * (upper_bound - lower_bound + 1) > 2 * n) {
      // only a small number of nodes to be picked from a huge universe
      
      Set< TwoDimensionalLongPoint > point_set =
              new HashSet<TwoDimensionalLongPoint>();

      for (int i = 0; i < n; ++i) {
        long x = random_.nextLong(lower_bound, upper_bound);
        long y = random_.nextLong(lower_bound, upper_bound);
        TwoDimensionalLongPoint pnew = new TwoDimensionalLongPoint(x, y);
        if (point_set.contains(pnew)) {
          --i;
          continue;
        }
        point_set.add(pnew);
        ret[i] = pnew;
      }

      return ret;

    } else {
      // small universe, big number
      ArrayList< TwoDimensionalLongPoint > points =
              new ArrayList<TwoDimensionalLongPoint>();
      for (long x = lower_bound; x <= upper_bound; ++x) {
        for (long y = lower_bound; y <= upper_bound; ++y) {
          points.add(new TwoDimensionalLongPoint(x, y));
        }
      }

      if (points.size() < n) {
        assert false;
      }
      Collections.shuffle(points, random_);

      for (int i = 0; i < n; ++i) ret[i] = points.get(i);
      return ret;
    }

  }

}
